/*
 * @lc app=leetcode.cn id=123 lang=cpp
 * @lcpr version=30204
 *
 * [123] 买卖股票的最佳时机 III
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 如果价格数组为空，直接返回 0
        if (prices.empty()) return 0;

        // 定义四个状态变量：
        // dp10: 第一次交易后，未持有股票的最大利润
        // dp11: 第一次交易后，持有股票的最大利润
        // dp20: 第二次交易后，未持有股票的最大利润
        // dp21: 第二次交易后，持有股票的最大利润
        int dp10 = 0, dp11 = -prices[0]; // 初始化第一次交易的状态
        int dp20 = 0, dp21 = -prices[0]; // 初始化第二次交易的状态

        // 遍历价格数组，从第 1 天开始（第 0 天已经初始化）
        for (int i = 1; i < prices.size(); ++i) {
            // 更新第二次交易的状态
            // dp20: 第二次交易后未持有股票的最大利润
            // 取当前 dp20 和 (第二次交易后卖出股票的利润) 的较大值
            dp20 = max(dp20, dp21 + prices[i]);

            // dp21: 第二次交易后持有股票的最大利润
            // 取当前 dp21 和 (第一次交易后未持有股票的利润减去当前价格) 的较大值
            dp21 = max(dp21, dp10 - prices[i]);

            // 更新第一次交易的状态
            // dp10: 第一次交易后未持有股票的最大利润
            // 取当前 dp10 和 (第一次交易后卖出股票的利润) 的较大值
            dp10 = max(dp10, dp11 + prices[i]);

            // dp11: 第一次交易后持有股票的最大利润
            // 取当前 dp11 和 (买入股票的负成本) 的较大值
            dp11 = max(dp11, -prices[i]);
        }

        // 返回最多两次交易后未持有股票的最大利润
        return dp20;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [3,3,5,0,0,3,1,4]\n
// @lcpr case=end

// @lcpr case=start
// [1,2,3,4,5]\n
// @lcpr case=end

// @lcpr case=start
// [7,6,4,3,1]\n
// @lcpr case=end

// @lcpr case=start
// [1]\n
// @lcpr case=end

 */

